1. Field of the Invention
The present invention relates generally to data storage systems having fault protection. More specifically, the invention relates to a RAID system that provides multiple-fault protection with increased write throughput capability.
2. Description of the Related Art
A continuing desire exists in the computer industry to consistently improve the performance and reliability of computer systems over time. For the most part, this desire has been achieved for the processor components of computer systems. Microprocessor performance has steadily improved over the years. However, the performance of the processor in a computer system is only one consideration associated with the overall performance of the computer system. For example, the computer memory system must be able to keep up with the demands of the processor or the processor will become stalled waiting for data from the memory system. Generally computer memory systems have been able to keep up with processor performance through increased capacities, lower access times, new memory architectures, caching, interleaving and other techniques.
Another critical aspect associated with the overall performance of a computer system is the I/O system performance. For most applications, the performance of the mass storage system or disk storage system serves a significant role in the I/O system performance. For example, when an application requires access to more data or information than it has room in allocated system memory, the data may be paged in/out of disk storage and to/from the system memory. Typically the computer system""s operating system copies a certain number of pages from the disk storage system to main memory. When a program needs a page that is not in main memory, the operating system copies the required page into main memory and copies another page back to the disk system. Processing may be stalled while the program is waiting for the page to be copied. If storage system performance does not keep pace with performance gains in other components of a computer system, then delays in storage system accesses may poison potential performance gains elsewhere.
One method that has been employed to increase the capacity and performance of disk storage systems is to employ an array of storage devices. An array improves storage performance by providing parallel data paths to read and write information over an array of disks. By reading and writing multiple disks simultaneously, the storage system performance may be greatly improved. For example, an array of four disks that can be read and written simultaneously may provide a data rate almost four times that of a single disk. However, using arrays of multiple disks comes with the disadvantage of increasing failure rates. In the example of a four disk array above, the mean time between failure (MTBF) for the array will generally be one-fourth that of a single disk. It is not uncommon for storage device arrays to include many more than four disks, shortening the mean time between failure from years to months or even weeks. Modern systems address this reliability issue by employing fault protection, or xe2x80x9credundancyxe2x80x9d, so that data lost from a device failure may be recovered.
A taxonomy of redundancy schemes has evolved for Redundant Array(s) of Independent Disks (RAID) that generally includes the following categories (list compiled by Advanced Computer and Network Corporation www.acnc.com): RAID 0, RAID 1, RAID 10, RAID 0+1, RAID 2, RAID 3, RAID 53, RAID 4, RAID 5 and RAID 6.
RAID 0 is something of a misnomer, as it does not provide any redundancy. It achieves enhanced I/O performance by breaking the data into blocks, and reading/writing the blocks in parallel on separate disks. The procedure of breaking a chunk of data into blocks and storing each of the blocks on a respective disk is commonly called xe2x80x9cstripingxe2x80x9d, because the chunk of data appears as a stripe across all the disks.
RAID 1 provides single fault-protection by providing duplicate disks for each of the disks in a RAID 0 array. This provides each disk in the system with a backup (also referred to as a xe2x80x9cshadowxe2x80x9d or a xe2x80x9cmirrorxe2x80x9d). Although the cost is high, the simplicity of design often makes this scheme desirable. In one configuration, multiple RAID 1 systems are coupled together with a RAID 0 controller, to form a system referred to as RAID 1+0 or RAID 10 system. RAID 0+1 is similar, but is constructed using two RAID 0 arrays, one of which mirrors the other.
RAID 2 provides fault protection by employing a Hamming code. The data words are encoded using a Hamming code to obtain corresponding code words. Each bit of the code word is then written to a respective drive.
RAID 3 provides single-fault protection by employing a parity-check bit and a dedicated parity drive. Generally the data disks are written synchronously and the corresponding parity-check data is generated dynamically and stored synchronously on the parity disk. Similarly, the data and parity disks are read synchronously and the verification (or data regeneration in the event of a disk failure) is performed dynamically. RAID 53 uses a RAID 0 architecture in which each of the disks are replaced with a RAID 3 system.
RAID 4 is similar to RAID 3, but the synchronous reading and writing requirement is removed. RAID 5 is a modification of RAID 4, in which the parity-check data is distributed across all of the disks, i.e. each of the disks store comparable amounts of data and comparable amounts of parity-check information. This causes the extra xe2x80x9cparity-checkxe2x80x9d disk to look statistically like all the other disks, which results in a more balanced load on each of the disks.
FIG. 1 illustrates a RAID 5 system, in which both data (denoted xe2x80x98Axe2x80x99, xe2x80x98Bxe2x80x99, xe2x80x98nxe2x80x99) and parity information (denoted xe2x80x98Pxe2x80x99) are striped across a storage device array. In a RAID 5 system, a stripe that spans all N of the disks in the array includes (Nxe2x88x921) data blocks and one block of the parity information that is computed over the (Nxe2x88x921) data blocks. The location of the parity block is shifted as a function of the stripe position. This balances the loading of the drives.
In a RAID5 system, when a subset of the data blocks within a stripe is updated, the parity block is typically also updated. The parity may be updated in either of two ways. The parity may be updated by reading the remaining unchanged data blocks and computing a new parity in conjunction with the new blocks (unmodified read/write stripe update), or reading the old version of the changed data blocks, comparing them with the new data blocks, and applying the difference to the parity (modified read/write stripe update). Generally, an unmodified read/write stripe update is preferable if the number of altered data blocks exceeds (Nxe2x88x92r)12, where r is the number of redundancy blocks in a stripe, and a modified read/write stripe update is preferable otherwise.
While some configurations of disk arrays such as RAID 5 systems provide relatively high performance and economical storage that are capable of rebuilding data in the event of single drive failures, if two drives fail, data is irretrievably lost. It is therefore sometimes desirable to provide configurations that are capable of rebuilding data in the event that multiple drives fail. RAID 6 is one such configuration. While the term xe2x80x9cRAID 6xe2x80x9d has sometimes suffered from inconsistent usage, the term is used herein to mean an extension of RAID 5 that employs two functions, sometimes referred to as P and Q parities, to provide double-fault protection. A primary difference between RAID 5 and RAID 6 is that RAID 6 uses twice as much redundancy for fault protection.
Each of the RAID schemes has advantages and disadvantages. It is thus often desirable to provide a single storage controller that can operate in any one of multiple storage modes. In addition, while systems that provide double fault protection such as RAID 6 configurations are generally known, some implementations of these systems suffer from relatively poor performance characteristics.
A data storage subsystem including an array of storage devices and a storage controller is disclosed. In one embodiment, the array of storage devices stores information in multiple stripes. Each stripe may include a plurality of data blocks and redundancy information in the form of plurality of redundancy blocks. The redundancy information may be generated using an nth order generator polynomial such as a Reed Solomon code. The storage controller may be configured to perform modified read/write stripe updates by: (a) reading original data from a subset of data blocks in a target stripe; (b) reading the original redundancy information for that stripe; (c) comparing the original data with the new data to determine a data difference; (d) calculating a redundancy difference from the data difference; (e) applying the redundancy difference to the original redundancy information to obtain updated redundancy information, (f) writing the new data and updated redundancy information to the target stripe.
In one particular embodiment, the storage controller may be configured to calculate redundancy blocks using a two-term, second order Reed-Solomon generator polynomial. The first redundancy term of a resulting code word polynomial is equal to a simple parity expression of the associated data words. This single redundancy term may thus be used to support RAID 5 configurations, and the storage controller may be configured to programmably support both RAID 5 configurations and RAID 6 configurations without extensive changes to the Reed-Solomon encoding and decoding functionality.